package RecursiveSearcher;

import java.util.List;

/**
 * @ClassName Hanota
 * @Description 汉诺塔问题
 * @Author ZJX
 * @Date 2024/9/11 14:37
 * @Version 1.0
 */

//   https://leetcode.cn/problems/hanota-lcci/description/

public class Hanota {
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        int n = a.size();
        dfs(a,b,c,n);
    }


    //    深搜
    private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
       if (n == 1){
           c.add(a.remove(a.size()-1));
           return;
       }
       dfs(a,c,b,n-1);
       c.add(a.remove(a.size()-1));
       dfs(b,a,c,n-1);
    }

}
